//希尔排序的思想基于插入排序，插入排序有时效率低下的原因是因为本来需要移动很远的距离，但是却是一个一个移动过去的
//就是对不同步长的数组进行插入排序。假如有六个元素的数组，然后分别选取步长是5,3,1那么就是
//间隔为5的那几个元素进行插入排序，然后间隔为3的那几个元素进行插入排序，最后是整体来一次插入排序
//经过研究（视频），推荐的步长序列是3x+1
//时间复杂度大概是nlogn级别
public class ShellSort extends Sort{
    public void MySort(int data[])
    {
        int length=data.length;
        int h=1;
        while(h<(length+1)/3)     //拿1到13个元素来说，在1到4的时候步长都为1，5到13步长都为4，没错的  
        {                         //但是如果用length/3的话，那么1到5的步长都为1,6到14的步长都为4，显然有点偏差
            h=3*h+1;
        }
        while(h>0)
        {
           for(int i=h;i<length;i++)                          //假设步长将数组分为若干个分组，那么算法的思路大概是从第二个分组开始遍历
           {                                                  //开始遍历后，对于每个元素用步长进行插入排序，也就是和其前面的元素进行比较
            for(int j=i;j>=h && data[j]<data[j-h];j-=h)       //正因为是插入排序，所以从开始之后，是一个一个地到最后一个元素
            {                                                 //因为左面是排序好的，右面是未排序的
               Exchange(data,j,j-h);
            }
           }
            h/=3;
        }
    }
    
}
//我开始想的是对于同一组需要排列的数（不是被步长分的组，而是需要进行比较排列的组）进行遍历
//这么实现应该也可以，无非就是外循环一个对h的循环，也就是在每个步长分组里的第几个数，
//然后再里面的循环是那个数一个个加上步长，得到下一个步长分组同位置的数
//最里面的循环是一个个通过步长进行的插入排序
//先前卡住主要有两个原因：1.想的循环过于复杂（或者说也没理清） 2.对整个过程的模拟逻辑没有搞清楚
//那么以后最重要的有两点：1.首先是按照整个算法的思路进行细节的模拟，2.再想办法进行优化
//拿我上面的三层循环进行举例，就明显过于复杂，很显然的是在同一个步长条件下，要对几乎所有的元素进行遍历，那么没必要多加一个循环提升理解复杂度
